package com.tgy.programmer_code_interview_guide._01_stack_queue;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/19/21 11:29 AM
 *
 *  https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 */
public class _08_柱状图中最大的矩形 {

    public static int largestRectangleArea(int[] heights) {

        if (heights == null || heights.length == 0) {

            return 0;
        }



        int len = heights.length;
        int[] leftToRight = new int[len];
        int[] rightToLeft = new int[len];

        for (int i = 0; i < len; i++) {
         //
            leftToRight[i] = -1;
            rightToLeft[i] = len;
        }

        for (int i = 1; i < len; i++) {

            int preIndex = i-1;

            while (preIndex >= 0) {

                if (heights[preIndex] < heights[i]) {

                    leftToRight[i] = preIndex;
                    break;
                }

                preIndex = leftToRight[preIndex];
            }

            int lastCur = len - i - 1;
            int nextIndex = lastCur + 1;

            while (nextIndex < len) {

                if (heights[nextIndex] < heights[lastCur]) {

                    rightToLeft[lastCur] = nextIndex;
                    break;
                }
                nextIndex = rightToLeft[nextIndex];
            }
        }


        int max = 0;

        for (int i = 0; i < len; i++) {

            max = Math.max(max, (rightToLeft[i] - leftToRight[i] - 1) * heights[i]);
        }

        return max;
    }

  public static void main(String[] args) {

      int max = largestRectangleArea(new int[]{2, 1, 1, 10, 2, 3});
      System.out.println(max);
  }
}
